The presence/absence of instructions and data in a processor cache memory has a significant impact on the processor performance. With main memory being 100 (and more) clocks “away” from the processor, the execution speed decreases dramatically if data/instructions have to be fetched from there. This arrangement creates a challenge for real-time applications that have to guarantee a certain response time to a triggering event. Most conventional cache designs employ a structure called “set associative”, meaning there are multiple cache locations available for a certain cache address. If two memory accesses alias/reference the same location in cache, multiple data items can be stored in alternate locations (sets), otherwise the later data will vacate and occupy the space of the first data. If there are several sets (e.g., 4 or 8), and all locations are occupied, a determination must be made as to which space is to be vacated to make room for a new data.
The “vacating” (replacement) policies often used are referred to as Random and Least Recently Used (LRU). With the Random method, the cache location to be vacated is selected randomly while with the LRU method, the location containing data that has been least recently accessed is vacated making the assumption that the data least recently accessed is of less importance.
Both methods fail to guarantee response time. Even if, in the case of LRU, if certain data is rarely used and statistically has less impact on performance, for a particular application, this can offer no performance “comfort”. In the case of hard real-time software (i.e., software in which failing to meet timing has serious consequences on system behavior, etc.), programmers use the method of reserving (locking) a portion of the cache and then re-arranging the code to ensure all critical data will permanently reside in the reserved area. This method certainly guarantees response time but at the expense of potentially “permanently” crippling the performance of other resident software.
Because of ever increasing processor speeds and with the proliferation of multi-core implementations, caches are growing in size. With more space available and more software running, the need to “police” the cache space allocation is obvious. The traditional LRU and Random methods have provided adequate performance in the past but they are unable to keep up with the evolution of processors.